package com.demo.datastructure.reorder.mergeSort;

/**
 * @description: 归并排序, 添加哨兵
 * @author: ljr
 * @time: 2021/5/4 16:15
 * @Since 1.1
 */
public class MyMergeSort2 {

    public static void mergeSort(int[] args, int n){
        mergeSortC(args,0,n-1);
    }

    private static void mergeSortC(int[] args, int p, int r) {
        if(p >= r) return;
        int q = (p+r)/2;
        mergeSortC(args,p,q);
        mergeSortC(args,q+1,r);
        merge(args,p,r,q);
    }

    private static void merge(int[] args, int p, int r, int q) {
        int[] leftArr = new int[q-p+2];
        int[] rightArr = new int[r-q+1];

        for (int i = 0; i <= q - p; i++) {
            leftArr[i] = args[p + i];
        }
        // 第一个数组添加哨兵（最大值）
        leftArr[q - p + 1] = Integer.MAX_VALUE;

        for (int i = 0; i < r - q; i++) {
            rightArr[i] = args[q + 1 + i];
        }
        // 第二个数组添加哨兵（最大值）
        rightArr[r-q] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        int k = p;

        while(k <= r){
            if (leftArr[i] <= rightArr[j]) {
                args[k++] = leftArr[i++];
            } else {
                args[k++] = rightArr[j++];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{11,8,3,9,7,1,2,5};
        MyMergeSort2.mergeSort(nums,8);
        for(int num : nums){
            System.out.println(num);
        }
    }

}
